今天繼續整理幾題動態規劃～
昨天放的幾題都是相對簡單的，今天會放幾題推演比較複雜或比較多維度的
明天整理狀態壓縮的題目

例題實戰

879. Profitable Schemes

[法一]暴力遞迴

一開始沒有特別好的思路，就先暴力遞迴..
暴力遞迴的思路就是基本就是先考慮搜索出每一種組合...
但答案要求的是回傳組合總數!
思考組合總數要怎麼計算
考慮一件物品：
(此物品被拿取的組合數)+(此物品被拿取的組合數)
當然，要能夠被拿取
再來討論一下基礎狀態：考慮第1件物品(下標0)時，若此時minProfit小於等於0時，至少會有一種組合，若此時成員夠完成第一項任務，則有兩種組合，若此時成員無法完成第一個任務，並且minProfit非小於等於0時
，就是0種組合數
以此種方式及基礎往下推演，就是暴力遞迴的寫法

[法二]DP

經由推演可以發現考慮第i個物品時，只與考慮i-1個物品時有關，所以可以寫成dp來計算
最後(代碼中)還可以進行經典的降維(要計算i只需要i-1)

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        /*由暴力法遞迴可以發現
        dp[i][j][k] 表示考慮前下標i的任務有j個成員最小利潤要k
        dp[i][j][k] = dp[i-1][j-gp[i]][k-pf[i]]+dp[i-1][j][k] {j-gp[i]>0}
        */
        const int mod = 1e9+7;
        int N = profit.size();
        vector<vector<vector<int>>> dp(N, vector<vector<int>>(n+1, vector<int>(minProfit+1, 0)));
        for(int i = 0; i<N; ++i){
            for(int j=0; j<=n; ++j){
                for(int k=0; k<=minProfit; ++k){
                    if(i==0){
                        //已經不需要更多利潤，但還可以加入任務
                        
                        //此時可以選或不選 2種
                        if(k==0&&j>=group[0]){
                            dp[0][j][0] = 2;
                        }
                        //不需要利潤了但不能加入任務
                        //不選 1種
                        else if(k==0){
                            dp[0][j][0] = 1;
                        }
                        //還需要利潤
                        //任務0可以滿足利潤k
                        else if(j>=group[0]&&profit[0]>=k){
                            dp[i][j][k] = 1;
                        }
                    }
                    else{
                        int pf_needed = k-profit[i];
                        if(pf_needed<0){
                            pf_needed = 0;
                        }
                        if(j-group[i]>=0)
                            dp[i][j][k]+=dp[i-1][j-group[i]][pf_needed]%mod;
                        dp[i][j][k]+=(dp[i-1][j][k]%mod);
                    }
                }
            }
        }
        return dp[N-1][n][minProfit]%mod;
        /*
        選i or 不選i
        dfs(idx-1, n-group[i],minProfit-profit[i])+ 
        dfs(idx-1, n, minProfit)
        */
        //return dfs(profit.size()-1,n,minProfit, group, profit);
    }
    //暴力dfs
    // int dfs(int idx, int n,int minProfit, vector<int>& gp, vector<int>& pf){
    //     int pick_idx = 0;
    //     int not_pick_idx = 0;
    //     if(idx==0){
    //         //already get enough profit
    //         if(minProfit<=0){
    //             if(n>=gp[0]){
    //                 return 2;
    //             }
    //             else{
    //                 return 1;
    //             }
    //         }
    //         else if(pf[0]>=minProfit&&n>=gp[0]){
    //             return 1;
    //         }
    //         else{
    //             return 0;
    //         }
    //     }
    //     else{
    //         //從這個遞迴可以看出決定現在的答案只跟idx-1有關，所以可以動態規劃
    //         if(n-gp[idx]>=0)//有辦法完成這項任務
    //             pick_idx = dfs(idx-1, n-gp[idx], minProfit-pf[idx], gp, pf); //pick i
    //         not_pick_idx = dfs(idx-1, n, minProfit, gp, pf);//dont pick i
    //     }
    //     return pick_idx+not_pick_idx;
    // }
};

714. 买卖股票的最佳时机含手续费

這題設定要用動態規劃來寫..
遞迴法會超時..
遞歸法：
但想法是一樣的，核心在於每一天可能發生的事有：持有時賣出、不賣出；不持有時買入、不買入
遞迴的想法就很簡單，直接遞迴傳入現在的狀態(持有、不持有、持有價值、現在獲利)嘗試，
動態規劃：
用兩個數組，存的數值都在於該狀態是不持有或持有，則可推導轉移方程
{持有[i] = Max(持有[i-1], 不持有[i-1]-價格[i])}
{不持有[i] = Max(不持有[i], 持有[i-1]+價格[i]-手續費)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size()==0){
            return 0;
        }
        vector<int> dp_hand(prices.size(), 0); //hand
        vector<int> dp_sold(prices.size(), 0); //sold
        dp_hand[0] = -prices[0];
        for(int i = 1; i<prices.size(); i++){
            dp_hand[i] = max(dp_hand[i-1], dp_sold[i-1]-prices[i]); //想法：能在第一天買就不要再更貴的第二天買
            dp_sold[i] = max(dp_hand[i-1] + prices[i]-fee, dp_sold[i-1]);
        }
        return dp_sold[dp_sold.size()-1]; // 最大值發生在最後是賣出的情況下(未賣出不可能是最佳解答)
        //return get_profit(prices, 0, 0, 0, fee);
    }
    // int get_profit(const vector<int>& prices, int storage_val, int cur_profit, int date, int fee){
    //     int sell_pro = -1, buy_pro = -1;
    //     if(date>prices.size()-1){
    //         return cur_profit;
    //     }
    //     if(storage_val){
    //         if(prices[date] < storage_val+fee)
    //             return get_profit(prices, storage_val, cur_profit, date+1, fee);
    //         //sell or dont sell
    //         sell_pro = max(get_profit(prices, storage_val, cur_profit, date+1, fee),
    //             get_profit(prices, 0, cur_profit+prices[date], date+1, fee)
    //         );
    //         return sell_pro;
    //     }
    //     else{
    //         //buy or dont buy
    //         buy_pro = max(get_profit(prices, prices[date], cur_profit-prices[date]-fee, date+1, fee), 
    //             get_profit(prices, storage_val, cur_profit, date+1, fee)
    //         );
    //         return buy_pro;
    //     }
    // }
};

停在原地的方案数

推演轉移方程
dp[i][j] = dp[i-1][j-1]+dp[i+1][j-1]+dp[i][j-1] ~~>注意邊界
dp[i][j] 代表從pos = 0開始到位置i的方法數
而dp[i][j]可能從 i. i-1, i+1推演，可得轉移方程
初始化的細節在於在arrLen足夠下，走到最遠的方法數為1(就只能一直走)

class Solution {
public:
    /* dp[pos][steps]  (from pos = 0)
    --> dp[i][j] = dp[i-1][j-1]+dp[i+1][j-1]+dp[i][j-1]
    */
    int numWays(int steps, int arrLen){
        int mod = 1000000007;
        arrLen = min(steps, arrLen);
        vector<vector<long>> dp(arrLen, vector<long>(steps+1, 0));
        // initialize
        for(int i = 0;i<arrLen; i++){
            dp[i][0] = 0;
        }
        for(int i = 0; i<=steps&&i<arrLen; i++){
            dp[i][i] = 1;
        }
        for(int j = 1; j<steps+1; j++){
            for(int i = 0; i<arrLen; i++){
                if(i==0)
                    dp[i][j] = (dp[i][j-1]+dp[i+1][j-1])%mod;
                else if(i==arrLen-1)
                    dp[i][j] = (dp[i][j-1]+dp[i-1][j-1])%mod;
                else
                    dp[i][j] = (dp[i-1][j-1]+dp[i+1][j-1]+dp[i][j-1])%mod;
            }
        }
        return dp[0][steps];
    }
};